//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 
//
// 示例： 
//
// 给定一个链表: 1->2->3->4->5, 和 n = 2.
//
//当删除了倒数第二个节点后，链表变为 1->2->3->5.
// 
//
// 说明： 
//
// 给定的 n 保证是有效的。 
//
// 进阶： 
//
// 你能尝试使用一趟扫描实现吗？ 
// Related Topics 链表 双指针 
// 👍 936 👎 0

package leetcode.editor.cn;

//Java：删除链表的倒数第N个节点
public class P19RemoveNthNodeFromEndOfList {

    //leetcode submit region begin(Prohibit modification and deletion)

    /*
     * 思路: right 右移，如果遍历的次数等于n，left也要开始往右移了，这样就能保证right结束时，left 刚好是倒n的前一个。 然后得判断一下 n 是第一个的情况
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 38.1 MB , 在所有 Java 提交中击败了 14.66% 的用户
     */

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (n <= 0) {
                return head;
            }
            int i = 0;      // i = 链表的长度 - 1
            ListNode left = head;
            ListNode right = head;
            // 1-> 1 2
            while (right.next != null) {
                right = right.next;
                i++;
                if (i > n) {
                    left = left.next;
                }
            }

            // 第一个  最后一个  长度为1  长度不为1  长度为N

            // n为第一个[链表长度]
            if (n == 1 + i) {
                if (i == 0) {
                    return null;
                } else {
                    return head.next;
                }
            } else if (n > i + 1) {
                return head;
            } else {
                left.next = left.next.next;
                return head;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P19RemoveNthNodeFromEndOfList().new Solution();
        ListNode node = new ListNode(2);
        node = add(node,1);
        node = solution.removeNthFromEnd(node, 1);
        System.out.println(node);
        // TO TEST
    }

    private static ListNode add(ListNode listNode, int x) {
        ListNode node = new ListNode(x);
        node.next = listNode;
        return node;
    }

}